package com.mamingchao.foundation.arraysort.mergesort;

import com.mamingchao.foundation.arraysort.Sortable;

import java.util.Arrays;

/**
 * 自己实现的，空间复杂度比较高
 * Created by mamingchao on 2021/3/10.
 */
public class MergeSortUpgrade {

    public static void main(String[] args) {
//        int[] arr = {1,3,5,7,9,2,4,6,8};
        int[] arr = {1,3,5,7,2,4,6,8};
        int[] newArr = sort(arr);
        for (int i = 0; i < newArr.length; i++) {
            System.out.print(newArr[i] + "\t");
        }
    }

    public static int[] sort(int[] arr) {

        if (arr.length <2) {
            //do nothing
            return arr;
        }

        //如果 只有两个值，顺序不对，就交换
        if (arr.length <3) {
            if (arr[1] < arr[0]) {
                arr[1] = arr[1] ^ arr[0];
                arr[0] = arr[1] ^ arr[0];
                arr[1] = arr[1] ^ arr[0];
            }
            return arr;
        }

        //计算对半分的中间索引值
        int mid = isOdd(arr.length) ?  (arr.length + 1)/2 : (arr.length)/2;


        //左边排好序
        int[] arr1 = sort(Arrays.copyOfRange(arr,0,mid));
        //右边排好序
        int[] arr2 = sort(Arrays.copyOfRange(arr,mid,arr.length));

        return merge(arr1,arr2);

    }


    /**
     * 对前半段和后半段排好序的数组进行 merge 排序
     * @param sortArr1
     * @param sortArr2
     * @return
     */
    private static int[] merge(int[] sortArr1,int[] sortArr2) {
        int[] newArr = new int[sortArr1.length + sortArr2.length];

        //子数组1 的索引
        int i = 0;
        //子数组2 的索引
        int j = 0;
        //新申请的大数组的索引
        int k = 0;

        while (i< sortArr1.length && j< sortArr2.length) {
            // 马老师说 如果不加 = ，当i 和j位置的值一样的时候，从后半截数组拿，会把归并变成不稳定
            //这个地方不太清楚，还需要 琢磨琢磨
//            if (array[i] <= array [j]) {
            newArr[k++] = sortArr1[i] <= sortArr2[j] ? sortArr1[i++] : sortArr2[j++];
        }

        //说明 subArr2 所有的element 都放到新数组里面去了
        while (i < sortArr1.length) newArr[k++] = sortArr1[i++];

        //说明 subArr1 所有的element 都放到新数组里面去了,subArr2的没全部放完，但剩下的都是大的，直接
        //把剩下的全部拿出来贴到新数组后面
        while (j < sortArr2.length)
            newArr[k++] = sortArr2[j++];

        return newArr;
    }

    private static boolean isOdd(int num){
        return num%2 == 0 ? true : false;
    }
}


